// ;[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

// TODO 返回指定索引前的数组
function printFibonacci(n) {
	if (n === 0) return [0]
	if (n === 1) return [0, 1]
	let arr = [0, 1]
	for (let i = 2; i <= n; i++) {
		arr.push(arr[i - 1] + (i >= 2 ? arr[i - 2] : 0))
	}
	return arr
}
console.log(printFibonacci(10))

// TODO 返回第n项的值(递归版 超过30容易崩盘)
function fb1(n) {
	if (n < 2) {
		return n
	} else {
		return fb1(n - 1) + fb1(n - 2)
	}
}
// console.log('fb1', fb1(2))

// TODO 返回第n项的值(每次循环保存值, memoization优化技术 ,保存计算的值,不在重复计算)
function fb2(n = 81) {
	if (n < 2) {
		return n
	}
	let res1 = 0
	let res2 = 1
	let num = 0
	for (let i = 2; i <= n; i++) {
		res1 = res2
		res2 = num + res2
		num = res1
	}
	return res2
}
// console.log('fb2',fb2(4))

// TODO 返回第n项的值(memoization优化技术 ,保存计算的值,不在重复计算)
function fb3(n, sum1 = 0, sum2 = 1) {
	if (n === 0) return 0
	if (n === 1) return sum2
	return fb3(n - 1, sum2, sum2 + sum1)
}
// console.log('fb3',fb3(4))

// f(0) 0
// f(1) 1
// f(2) f(1,1,1) 1
// f(3) f(2,1,1) f(1,1,2) 2
// f(4) f(3,1,1) f(2,1,2) f(1,2,3) 3
// f(5) f(4,1,1) f(3,1,2) f(2,2,3) f(1,3,5) 5
// f(6) f(5,1,1) f(4,1,2) f(3,2,3) f(2,3,5) f(1,5,8) 8

// TODO 输出 100 以内的菲波那切数列
function fib(n) {
	let a = 0
	let b = 1
	let r = [0]
	while (b < n) {
		r.push(b)
		;[a, b] = [b, a + b]
	}
	return r
}
// console.log('fib', fib(4))
